package BinaryTree;//给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
//
// 叶子节点 是指没有子节点的节点。 
//
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：[[5,4,11,2],[5,8,4,5]]
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], targetSum = 0
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点总数在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
// 
// 
// Related Topics 树 深度优先搜索 回溯 二叉树 👍 612 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class pathSumII {

    List<List<Integer>> res = new ArrayList<>();  //全局结果集
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        /**
         * 递归回溯
         * */
        if(root==null){
            return  res;
        }
        List<Integer> list = new ArrayList<>();
        getAllPaths(root, list,targetSum - root.val);
        return res;

    }
    //1.参数和返回值,因为要遍历每一个不需要返回值，2.结束条件 3.单层逻辑
    private void getAllPaths(TreeNode root, List<Integer> list, int target){
//        if(root == null){
//            return;
//        }
        list.add(root.val);
        if(root.left==null && root.right==null){
            //到叶子节点且符合要求
            if(target==0){
                //为什么？ 必须新建
                //因为path一直在变，如果不开新空间的话，也会影响到res中已保存的path
                res.add(new ArrayList<>(list));  //当前路径加入结果集
            }
            return;
        }
        if(root.left!=null){
            getAllPaths(root.left, list, target - root.left.val);
            list.remove(list.size()-1);  //回溯
        }
        if(root.right!=null){
            getAllPaths(root.right, list, target - root.right.val);
            list.remove(list.size()-1);  //回溯
        }

    }

    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        /**
         * 迭代法 利用栈模拟递归 ，逻辑相同
         * */
        if(root==null){
            return res;
        }
        List<Integer> path = new ArrayList<>();
        Stack<Object> stack = new Stack<Object>();  //栈保存当前节点和到当前节点的和，
        stack.push(root);
        stack.push(root.val);
        while(!stack.isEmpty()){
            int sum = (int) stack.pop();
            TreeNode curr = (TreeNode) stack.pop();
            path.add(curr.val);
            //到叶子节点 且判断是否符合要求
            if(curr.left==null && curr.right==null){
                if(sum==targetSum){
                    res.add(new ArrayList<>(path));
                }else{
                    path.remove(path.size()-1);
                }
            }
            if(curr.right!=null){
                stack.push(curr.right);
                stack.push(curr.right.val + sum);
            }
            if(curr.left!=null){
                stack.push(curr.left);
                stack.push(curr.left.val + sum);
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
